.. _глава_64_start:

Шаблоны
=======

.. index::
    шаблон
    template

Шаблоны - это функция, которая позволяет описывать код в виде шаблона, чтобы компилятор
компилятора для автоматической генерации программного кода. Часть исходного кода может быть
оставлены компилятору для заполнения до тех пор, пока эта часть не будет использована в программе.
Шаблоны очень полезны, особенно в библиотеках, поскольку они позволяют писать
общие алгоритмы и структуры данных, вместо того чтобы привязывать их к конкретным типам.
По сравнению с поддержкой шаблонов в других языках, шаблоны в D очень
мощные и обширные. Я не буду вдаваться во все подробности шаблонов в этой
главе. Я рассмотрю только шаблоны функций, структур и классов и только параметры шаблонов типов. Подробнее о шаблонах мы поговорим в главе
Больше шаблонов (:ref:`Дополнительная информация о шаблонах<глава_78_start>`).
Полный справочник по шаблонам D можно найти в книге Филиппа Сиго D Templates: A Tutorial1.(external link ???)
Чтобы увидеть преимущества шаблонов, давайте начнем с функции, которая печатает значения в
круглых скобках:

.. code-block:: d

    void printInParens(int value)
    {
        writefln("(%s)", value);
    }

Поскольку параметр указан как int, эта функция может использоваться только со значениями
значениями типа int или значениями, которые могут быть автоматически преобразованы в int. Для
Например, компилятор не позволит вызвать ее с типом с плавающей точкой.
Предположим, что требования программы изменились, и в ней появились другие типы
необходимо выводить в круглых скобках. Одним из решений этой проблемы может быть
воспользоваться преимуществами перегрузки функций и обеспечить перегрузку функции для
всех типов, с которыми используется функция:

.. code-block:: d

    // The function that already exists
    void printInParens(int value)
    {
        writefln("(%s)", value);
    }

    // Overloading the function for 'double'
    void printInParens(double value)
    {
        writefln("(%s)", value);
    }

Это решение не очень хорошо масштабируется, потому что на этот раз функция не может быть использована
например, с вещественным или любым другим пользовательским типом. Хотя можно перегрузить функцию
функцию для других типов, затраты на это могут оказаться непомерными.
Важным замечанием здесь является то, что независимо от типа параметра,
содержимое перегрузок будет в общем случае одинаковым: одно единственное выражение
выражение writefln().
Такая общность часто встречается в алгоритмах и структурах данных. Например, алгоритм
алгоритм двоичного поиска не зависит от типа элементов: Речь идет о
конкретных шагах и операциях поиска. Аналогично, структура данных связанного списка
не зависит от типа элементов: Связный список - это всего лишь способ
элементы хранятся в контейнере, независимо от их типа.
В таких ситуациях полезны шаблоны: Если часть кода описана как
шаблона, компилятор автоматически генерирует перегрузки того же кода
в соответствии с реальным использованием этого кода в программе. Как я уже говорил выше, в этой главе я рассмотрю только шаблоны функций, структур,
и шаблоны классов, а также параметры шаблонов типов

.. index::
    шаблоны функций

Шаблоны функций
---------------

Определяя функцию как шаблон, вы оставляете один или несколько типов, которые она использует
неопределенными, чтобы компилятор вывел их позже.
Типы, которые остаются неопределенными, определяются в списке параметров шаблона
список параметров, который находится между именем функции и списком параметров функции
список параметров. По этой причине шаблоны функций имеют два списка параметров: список параметров шаблона и список параметров функции.
список параметров шаблона и список параметров функции:

.. code-block:: d

    void printInParens(T)(T value)
    {
        writefln("(%s)", value);
    }

T в приведенном выше списке параметров шаблона означает, что T может быть любым типом.
Хотя T - это произвольное имя, оно является сокращением от слова "тип" и очень часто встречается
в шаблонах.
Поскольку T представляет любой тип, шаблонное определение printInParens()
достаточно, чтобы использовать его практически с любым типом, включая пользовательские
и пользовательскими:

.. code-block:: d

    import std.stdio;

    void printInParens(T)(T value)
    {
        writefln("(%s)", value);
    }

    void main()
    {
        printInParens(42); // with int
        printInParens(1.2); // with double
        auto myValue = MyStruct();
        printInParens(myValue); // with MyStruct
    }

    struct MyStruct
    {
        string toString() const
        {
            return "hello";
        }
    }

Компилятор учитывает все варианты использования printInParens() в программе и
генерирует код для поддержки всех этих применений. Программа компилируется так, как если бы функция
была перегружена явно для int, double и MyStruct:

.. code-block:: d

    /* Note: These functions are not part of the source
     * code. They are the equivalents of the functions that
     * the compiler would automatically generate. */
    void printInParens(int value)
    {
        writefln("(%s)", value);
    }

    void printInParens(double value)
    {
        writefln("(%s)", value);
    }

    void printInParens(MyStruct value)
    {
        writefln("(%s)", value);
    }

На выходе программы получаются различные инстансы шаблона

.. code-block:: console

    (42)
    (1.2)
    (hello)

Каждый параметр шаблона может определять более одного параметра функции. Для
например, оба параметра функции и возвращаемый тип следующей
функции-шаблона определяются ее единственным параметром-шаблоном:

.. code-block:: d

    /* Returns a copy of 'slice' except the elements that are
        * equal to 'value'. */

        T[] removed(T)(const(T)[] slice, T value)
    {
        T[] result;
        foreach (element; slice)
        {
            if (element != value)
            {
                result ~= element;
            }
        }
        return result;
    }

Более одного параметра шаблона
------------------------------

Давайте изменим шаблон функции, чтобы он также принимал символы круглых скобок:

.. code-block:: d

    void printInParens(T)(T value, char opening, char closing)
    {
        writeln(opening, value, closing);
    }

Теперь мы можем вызывать одну и ту же функцию с разными наборами круглых скобок:

.. code-block:: d

    printInParens(42, '<', '>');

Хотя возможность указать круглые скобки делает функцию более удобной,
указание типа скобок как char делает ее менее гибкой, поскольку
невозможно вызвать функцию с символами типа wchar или dchar:

.. code-block:: d

    printInParens(42, '→', '←'); // ← ошибка компиляции

.. code-block:: console

    Error: template deneme.printInParens(T) cannot deduce template function from argument types !()(int,wchar,wchar)

Одним из решений может быть указание типа скобок как dchar, но этого
все равно будет недостаточно, поскольку в этом случае функцию нельзя будет вызвать, например, с типом
string или пользовательскими типами.
Другое решение - оставить тип круглых скобок на усмотрение компилятора.
Определить дополнительный параметр шаблона вместо конкретного char будет
достаточно:

.. code-block:: d

    void printInParens(T, ParensType)(T value,    ParensType opening,ParensType closing)
    {
        writeln(opening, value, closing);
    }

Значение нового параметра шаблона аналогично параметру T: ParensType может быть
любой тип.
Теперь можно использовать множество различных типов круглых скобок. Ниже приведены
с wchar и string:

.. code-block:: d

    printInParens(42, '→', '←');
    printInParens(1.2, "-=", "=-");

.. code-block:: console

    →42←
    -=1.2=-

Гибкость функции printInParens() была увеличена, так как теперь она работает корректно
для любой комбинации T и ParensType при условии, что эти типы могут быть напечатаны
с помощью writeln().

Вывод типа
-----------

Решение компилятора о том, какой тип использовать для параметра шаблона, называется
выводом типа.
Продолжая последний пример, компилятор решает следующие
типы в соответствии с двумя вариантами использования шаблона функции:
* int и wchar, когда выводится 42
* double и string, когда выводится 1.2.
Компилятор может выводить типы только из типов значений параметров, которые
которые передаются в шаблоны функций. Хотя обычно компилятор может вывести
типы без всякой двусмысленности, бывают случаи, когда типы должны быть указаны
программиста.

Явное указание типа
-------------------

Иногда компилятор не может вывести параметры шаблона.
Это может произойти, если типы не указаны в списке параметров функции
в списке параметров функции. Когда параметры шаблона не связаны с параметрами функции
компилятор не может вывести типы шаблонных параметров.
Чтобы увидеть пример этого, давайте спроектируем функцию, которая задает вопрос пользователю
пользователю, считывает значение в качестве ответа и возвращает это значение. Кроме того, давайте сделаем
эту функцию шаблоном, чтобы ее можно было использовать для чтения любого типа ответа:

.. code-block:: d

    T getResponse(T)(string question)
    {
        writef("%s (%s): ", question, T.stringof);
        T response;
        readf(" %s", &response);
        return response;
    }

Этот шаблон функции будет очень полезен в программах для чтения различных типов
значений из входных данных. Например, чтобы считать информацию о пользователе, мы можем
представить себе, что мы вызываем его, как в следующей строке:

.. code-block:: d

    getResponse("What is your age?");

К сожалению, этот вызов не дает компилятору никаких подсказок о том, каким должен быть
должен быть параметр шаблона T. Известно только, что вопрос передается в
в функцию в виде строки, но тип возвращаемого значения определить невозможно:

.. code-block:: console

    Error: template deneme.getResponse(T) cannot deduce template function from argument types !()(string)

В таких случаях параметры шаблона должны быть указаны программистом в явном виде
программистом. Параметры шаблона указываются в круглых скобках после
восклицательного знака:

.. code-block:: d

    getResponse!(int)("What is your age?");

Инстанцирование шаблона
------------------------

Автоматическая генерация кода для определенного набора значений параметров шаблона называется
называется инстанцированием этого шаблона для конкретного набора значений параметров.
Например, to!string и to!int - это два разных инстанцирования шаблона функции to
шаблона функции.
Как я еще раз упомяну в отдельном разделе ниже, различные инстанцирования
шаблонов создают разные и несовместимые типы.

Специализации шаблонов
----------------------

Хотя шаблон функции getResponse() теоретически может быть использован для любого
шаблонного типа, код, который генерирует компилятор, может быть пригоден не для каждого
типа. Предположим, что у нас есть следующий тип, представляющий точки в двухмерном
мерном пространстве:

.. code-block:: d

    struct Point
    {
        int x;
        int y;
    }

Хотя инстанцирование getResponse() для типа Point само по себе будет  условно правильным,
то сгенерированный вызов readf() для Point не может быть скомпилирован. Это происходит потому, что
стандартная библиотечная функция readf() не знает, как читать объект Point.
Две строки, которые фактически считывают ответ, будут выглядеть следующим образом в
инстанция Point шаблона функции getResponse():

.. code-block:: d

    Point response;
    readf(" %s", &response); // ← ошибка компиляции

Один из способов чтения объекта Point заключается в том, чтобы считать значения членов x и y
отдельно, а затем построить объект Point из этих значений.
Предоставление специального определения шаблона для конкретного параметра шаблона
называется специализацией шаблона. Специализация определяется типом
после символа : в списке параметров шаблона. Специализация Point для
шаблона функции getResponse() может быть определена следующим образом:

.. code-block:: d

Один из способов чтения объекта Point заключается в том, чтобы считать значения членов x и y
отдельно, а затем построить объект Point из этих значений.
Предоставление специального определения шаблона для конкретного параметра шаблона
называется специализацией шаблона. Специализация определяется типом
после символа : в списке параметров шаблона. Специализация Point для
шаблона функции getResponse() может быть определена следующим образом:

.. code-block:: d

    // The general definition of the function template (same as before)
    T getResponse(T)(string question)
    {
        writef("%s (%s): ", question, T.stringof);
        T response;
        readf(" %s", &response);
        return response;
    }

    // The specialization of the function template for Point
    T getResponse(T : Point)(string question)
    {
        writefln("%s (Point)", question);
        auto x = getResponse!int("  x");
        auto y = getResponse!int("  y");
        return Point(x, y);
    }

Обратите внимание, что специализация использует общее определение функции
getResponse() для чтения двух значений int, которые будут использоваться в качестве значений членов x и y
членов.
Вместо инстанцирования самого шаблона компилятор теперь использует приведенную выше специализацию
вышеуказанную специализацию всякий раз, когда вызывается getResponse() для типа Point:

.. code-block:: d

    auto center = getResponse!Point("Where is the center?");

Предположим, что пользователь ввел значения 11 и 22:

.. code-block:: d

    Where is the center? (Point)
    x (int): 11
    y (int): 22

Вызовы getResponse!int() направлены на общее определение шаблона
шаблона, а вызовы getResponse!Point() направлены на специализацию Point
его специализации.
В качестве другого примера рассмотрим использование того же шаблона со строкой. Как
вы помните из главы "Строки" (:ref:`Строки<Строки>`), readf() считывает все
символы из входных данных как часть одной строки до конца
ввода. По этой причине стандартное определение функции getResponse() не будет
полезным при чтении строковых ответов:

.. code-block:: d

    // Reads the entire input, not only the name!
    auto name = getResponse!string("What is your name?")

Мы можем предоставить специализацию шаблона и для строки. Следующая
специализация читает только строку:

.. code-block:: d

   T getResponse(T : string)(string question)
    {
        writef("%s (string): ", question);
        // Read and ignore whitespace characters which have
        // presumably been left over from the previous user input
        string response;
        do
        {
            response = strip(readln());
        }
        while (response.length == 0);
        return response;
    }


Шаблоны структур и классов
--------------------------

Структура Point имеет ограничения: поскольку два ее члена
определены как int, она не может представлять дробные значения координат. Это
Это ограничение можно снять, если определить структуру Point как шаблон.
Сначала добавим функцию-член, которая возвращает расстояние до другого объекта Point
объекта:

.. code-block:: d

    import std.math;

    // ...
    struct Point
    {
        int x;
        int y;
        int distanceTo(Point that) const
        {
            immutable real xDistance = x - that.x;
            immutable real yDistance = y - that.y;
            immutable distance = sqrt((xDistance * xDistance) + (yDistance * yDistance));
            return cast(int) distance;
        }
    }


Такое определение Point подходит, когда требуемая точность относительно невелика:
Оно может вычислить расстояние между двумя точками с точностью до километра, например
например, между центром и филиалами организации:

.. code-block:: d

    auto center = getResponse!Point("Where is the center?");
    auto branch = getResponse!Point("Where is the branch?");
    writeln("Distance: ", center.distanceTo(branch));


К сожалению, Point неадекватен если требуется более высщкаятлчность, чем та которую может обеспечить int.
Структуры и классы также можно определять как шаблоны, указывая список параметров шаблона
после их имен. Например, Point можно определить как структуру
указав параметр шаблона и заменив им int параметром:

.. code-block:: d

   struct Point(T)
    {
        T x;
        T y;
        T distanceTo(Point that) const
        {
            immutable real xDistance = x - that.x;
            immutable real yDistance = y - that.y;
            immutable distance = sqrt((xDistance * xDistance) + (yDistance * yDistance));
            return cast(T) distance;
        }
    }


Since structs and classes are not functions, they cannot be called with
parameters. This makes it impossible for the compiler to deduce their template
parameters. The template parameter list must always be specified for struct and
class templates:

Поскольку структуры и классы не являются функциями, их нельзя вызывать. Поэтому
компилятор не может вывести параметры шаблона; типы должны быть указаны явно
на это следует обратить внимание:

.. code-block:: d

    auto center = Point!int(0, 0);
    auto branch = Point!int(100, 100);
    writeln("Distance: ", center.distanceTo(branch));

Приведенные выше определения заставляют компилятор генерировать код для экземпляра int
шаблона Point, что эквивалентно его предыдущему нешаблонному
определению. Однако теперь его можно использовать с любым типом. Например, когда требуется большая
точности, например, с типом double:

.. code-block:: d

    auto point1 = Point!double(1.2, 3.4);
    auto point2 = Point!double(5.6, 7.8);
    writeln(point1.distanceTo(point2));

Хотя сам шаблон был определен независимо от конкретного типа,
его единое определение позволяет представлять точки с различной точностью.
Простое преобразование Point в шаблон приведет к ошибкам компиляции в коде
который уже был написан в соответствии с его нешаблонным определением. Для
например, теперь специализация Point функции getResponse() не может быть скомпилирована:

.. code-block:: d

   T getResponse(T : Point)(string question)
    { // ← compilation ERROR
        writefln("%s (Point)", question);
        auto x = getResponse!int("  x");
        auto y = getResponse!int("  y");
        return Point(x, y);
    }


Причина ошибки компиляции заключается в том, что сам Point больше не является типом:
Point теперь является шаблоном struct. Только инстансы этого шаблона будут
считаться типами. Чтобы корректно специализировать
getResponse() для любого инстанса Point:

.. code-block:: d

    Point!T getResponse(T : Point!T)(string question) // 2, 1
    {
        writefln("%s (Point!%s)", question, T.stringof); // 5
        auto x = getResponse!T("  x"); // 3a
        auto y = getResponse!T("  y"); // 3b
        return Point!T(x, y); // 4
    }


#. Для того чтобы эта специализация шаблона поддерживала все инстансы Point,
список параметров шаблона должен упоминать Point!T. Это просто означает, что
что специализация getResponse() предназначена для Point!T, независимо от T. Эта специализация будет соответствовать Point!int
специализация будет соответствовать Point!int, Point!double и т. д.
#. Аналогично, чтобы вернуть правильный тип в качестве ответа, тип возврата должен быть
также должен быть указан как Point!T.
#. Поскольку типы членов x и y в Point!T теперь T, а не int,
эти члены должны быть прочитаны вызовом getResponse!T(), а не
getResponse!int(), поскольку последний вариант будет корректен только для Point!int.
#. Как и в пунктах 1 и 2, тип возвращаемого значения - Point!T.
#. Чтобы вывести имя типа точно для каждого типа, как в Point!int,
Point!double и т. д., используется T.stringof.


Параметры шаблона по умолчанию
-------------------------------

Иногда бывает неудобно предоставлять типы параметров шаблона каждый раз, когда
шаблона, особенно когда этот тип почти всегда определенный. Например,
например, функция getResponse() может почти всегда вызываться для типа int в
и только в некоторых местах - для типа double.
Можно указать типы по умолчанию для параметров шаблона, которые
предполагаются, если типы не указаны явно. Типы параметров по умолчанию
указываются после символа =:

.. code-block:: d

    T getResponse(T = int)(string question)
    {
    // ...
    }
    // ...
    auto age = getResponse("What is your age?");

Поскольку при вызове getResponse() выше не был указан тип, int ,будет типом по умолчанию int, и вызов оказывается эквивалентным
getResponse!int().
Параметры шаблона по умолчанию могут быть указаны также для шаблонов struct и class
но в этом случае список параметров шаблона должен быть записан всегда, даже если он
даже если он пуст:

.. code-block:: d

    struct Point(T = int)
    {
    // ...
    }
    // ...
    Point!() center;

Аналогично значениям параметров функции по умолчанию, как мы видели в главе Переменное Количество параметров (:ref:`Переменное количество параметров<глава_48_start>`),
параметры шаблона по умолчанию могут быть указаны
для всех параметров шаблона или для последних:

.. code-block::

    void myTemplate(T0, T1 = int, T2 = char)()
    {
    // ...
    }

Последние два параметра шаблона этой функции можно не указывать, но первый первый обязателен:

.. code-block:: d

    myTemplate!string();

В этом случае второй и третий параметры являются int и char соответственно.

Каждая инстанция шаблона дает отдельный тип
--------------------------------------------

Каждая инстанция шаблона для заданного набора типов считается
отдельным типом. Например, Point!int и Point!double - это отдельные типы:

.. code-block:: d

    Point!int point3 = Point!double(0.25, 0.75);

Эти различные типы не могут быть использованы в операции присвоения, описанной выше:

.. code-block:: console

    Error: cannot implicitly convert expression (Point(0.25,0.75)) of type Point!(double) to Point!(int

Шаблоны это возможность времени компиляции
------------------------------------------

Шаблоны - это полностью функция времени компиляции. Экземпляры шаблонов
генерируются компилятором во время компиляции.

Пример шаблона класса: структура данных стека
---------------------------------------------

Шаблоны структур и классов широко используются при реализации структур данных
структур данных. Давайте спроектируем контейнер стека, который сможет содержать любой тип.
Стек - одна из самых простых структур данных. Он представляет собой контейнер, в котором
элементы концептуально располагаются друг на друге, как в стопке
бумаги. Новые элементы помещаются сверху, и доступ к ним осуществляется только к самому верхнему элементу. Когда
элемент удаляется, он всегда остается самым верхним.
Если мы также определим свойство, возвращающее общее количество элементов в
стеке, то все операции этой структуры данных будут выглядеть следующим образом:
* Добавить элемент (push())
* Удаление элемента (pop())
* Доступ к самому верхнему элементу (.top)
* Количество элементов (.length)
Для хранения элементов можно использовать массив таким образом, чтобы последний элемент массива
будет представлять самый верхний элемент стека. Наконец, он может быть определен
как шаблон класса, чтобы иметь возможность содержать элементы любого типа:

.. code-block:: d

    class Stack(T)
    {
    private:
        T[] elements;
    public:
        void push(T element)
        {
            elements ~= element;
        }

        void pop()
        {
            --elements.length;
        }

        T top() const
        {
            return elements[$ - 1];
        }

        size_t length() const
        {
            return elements.length;
        }
    }

Вот блок unittest для этого класса, который использует его инстанцию int:

.. code-block:: d

    unittest
    {
        auto stack = new Stack!int;
        // The newly added element must appear on top
        stack.push(42);
        assert(stack.top == 42);
        assert(stack.length == 1);
        // .top and .length should not affect the elements
        assert(stack.top == 42);
        assert(stack.length == 1);
        // The newly added element must appear on top
        stack.push(100);
        assert(stack.top == 100);
        assert(stack.length == 2);
        // Removing the last element must expose the previous one
        stack.pop();
        assert(stack.top == 42);
        assert(stack.length == 1);
        // The stack must become empty when the last element is
        // removed
        stack.pop();
        assert(stack.length == 0);
    }

Чтобы воспользоваться преимуществами этого шаблона класса, давайте попробуем использовать его на этот раз с пользовательским
определенным пользователем типом. В качестве примера приведем модифицированную версию Point:

.. code-block:: d

    struct Point(T)
    {
        T x;
        T y;
        string toString() const
        {
            return format("(%s,%s)", x, y);
        }
    }

Стек, содержащий элементы типа Point!double, может быть определен следующим образом:

.. code-block:: d

    auto points = new Stack!(Point!double);

Вот тестовая программа, которая сначала добавляет десять элементов в этот стек, а затем удаляет их
их по одному:

.. code-block:: d

    import std.stdio;
    import std.random;

    struct Point(T)
    {
      T x;
      T y;
      string toString() const
      {
          return format("(%s,%s)", x, y);
      }
    }
    // Returns a random value between -0.50 and 0.50.
    double random_double()
    out (result)
    {
      assert((result >= -0.50) && (result < 0.50));
    }
    do
    {
      return (double(uniform(0, 100)) - 50) / 100;
    }
    // Returns a Stack that contains 'count' number of random
    // Point!double elements.
    Stack!(Point!double) randomPoints(size_t count)
    out (result)
    {
      assert(result.length == count);
    }
    do
    {
      auto points = new Stack!(Point!double);
      foreach (i; 0 .. count)
      {
          immutable point = Point!double(random_double(),
              random_double());
          writeln("adding  : ", point);
          points.push(point);
      }
      return points;
    }

    void main()
    {
      auto stackedPoints = randomPoints(10);
      while (stackedPoints.length)
      {
          writeln("removing: ", stackedPoints.top);
          stackedPoints.pop();
      }
    }

Как показывает вывод программы, элементы удаляются в обратном
порядке, в котором они были добавлены:

.. code-block:: console

    adding  : (-0.02,-0.01)
    adding  : (0.17,-0.5)
    adding  : (0.12,0.23)
    adding  : (-0.05,-0.47)
    adding  : (-0.19,-0.11)
    adding  : (0.42,-0.32)
    adding  : (0.48,-0.49)
    Templates
    409
    adding  : (0.35,0.38)
    adding  : (-0.2,-0.32)
    adding  : (0.34,0.27)
    removing: (0.34,0.27)
    removing: (-0.2,-0.32)
    removing: (0.35,0.38)
    removing: (0.48,-0.49)
    removing: (0.42,-0.32)
    removing: (-0.19,-0.11)
    removing: (-0.05,-0.47)
    removing: (0.12,0.23)
    removing: (0.17,-0.5)
    removing: (-0.02,-0.01)

Пример шаблона функции: алгоритм бинарного поиска
-------------------------------------------------

Бинарный поиск - это самый быстрый алгоритм поиска элемента среди
элементов уже отсортированного массива. Это очень простой алгоритм: Рассматривается элемент в
посередине; если этот элемент является искомым, то
поиск окончен. Если нет, то алгоритм повторяется для элементов, которые находятся
либо слева, либо справа от среднего элемента,
в зависимости от того, больше или меньше искомый элемент, чем средний
элемент.
Алгоритмы, которые повторяются на меньшем диапазоне исходных элементов
являются рекурсивными. Запишем алгоритм двоичного поиска рекурсивно, вызывая сам себя.
Прежде чем преобразовывать его в шаблон, давайте сначала напишем эту функцию так, чтобы она поддерживала только
массивы int. Позже мы сможем легко преобразовать ее в шаблон, добавив шаблонный
список параметров и заменив соответствующие ints в ее определении на Ts. Вот
алгоритм двоичного поиска, который работает с массивами int:

.. code-block:: d

    import std.string;

    /* This function returns the index of the value if it exists
    * in the array, size_t.max otherwise. */
    size_t binarySearch(const int[] values, int value)
    {
        // The value is not in the array if the array is empty.
        if (values.length == 0)
        {
            return size_t.max;
        }
        immutable midPoint = values.length / 2;
        if (value == values[midPoint])
        {
            // Found.
            return midPoint;
        }
        else if (value < values[midPoint])
        {
            // The value can only be in the left-hand side; let's
            // search in a slice that represents that half.
            return binarySearch(values[0 .. midPoint], value);
        }
        else
        {
            // The value can only be in the right-hand side; let's
            // search in the right-hand side.
            auto index =
                binarySearch(values[midPoint + 1 .. $], value);
            if (index != size_t.max)
            {
                // Adjust the index; it is 0-based in the
                // right-hand side slice.
                index += midPoint + 1;
            }
            return index;
        }
        assert(false, "We should have never gotten to this line");
    }

Приведенная выше функция реализует этот простой алгоритм за четыре шага:
* Если массив пуст, верните size_t.max, чтобы указать, что значение не было
не найдено.
* Если элемент в средней точке равен искомому значению, то верните
индекс этого элемента.
* Если значение меньше, чем элемент в средней точке, то повторите тот же
алгоритм для левой стороны.
* В противном случае повторите тот же алгоритм с правой стороны.
Вот блок unittest, который тестирует функцию:

.. code-block:: d

    unittest
    {
        auto array = [1, 2, 3, 5];
        assert(binarySearch(array, 0) == size_t.max);
        assert(binarySearch(array, 1) == 0);
        assert(binarySearch(array, 4) == size_t.max);
        assert(binarySearch(array, 5) == 3);
        assert(binarySearch(array, 6) == size_t.max);
    }

Теперь, когда функция реализована и протестирована для int, мы можем преобразовать
int появляется только в двух местах в определении шаблона:

.. code-block::

    size_t binarySearch(const int[] values, int value) {
    // ... int does not appear here ...
    }

Тип int, который появляется в списке параметров, являются типoм элементов и их значений. Указание их в качестве параметров шаблона достаточно, чтобы сделать этот
алгоритм шаблонным и пригодным для использования и с другими типами:

.. code-block:: d

    size_t binarySearch(T)(const T[] values, T value) {
    // ...
    }

Этот шаблон функции можно использовать с любым типом, который соответствует операциям которые применяются к этому типу в шаблоне. В функции binarySearch() элементы
используются только с операторами сравнения == и <:

.. code-block:: d

    if (value == values[midPoint]) {
    // ...
    } else if (value < values[midPoint]) {
    // ...

По этой причине Point еще не готов к использованию с binarySearch():

.. code-block:: d

     import std.string;

    struct Point(T)
    {
        T x;
        T y;
        string toString() const
        {
            return format("(%s,%s)", x, y);
        }
    }

    void main()
    {
        Point!int[] points;
        foreach (i; 0 .. 15)
        {
            Templates 411 points ~= Point!int(i, i);
        }
        assert(binarySearch(points, Point!int(10, 10)) == 10);
    }

The program above would cause a compilation error:

.. code-block:: console

    Error: need member function opCmp() for struct const(Point!(int)) to compare

Согласно сообщению об ошибке, для Point необходимо определить opCmp(). opCmp()
была рассмотрена в главе (:ref:`Перегрузка операторов<глава_53_start>`).

.. code-block:: d

    struct Point(T)
    {
        // ...
        int opCmp(const ref Point that) const
        {
            return (x == that.x
                    ? y - that.y : x - that.x);
        }
    }

Резюме
--------

Другие возможности шаблонов мы рассмотрим в следующей главе (:ref:`Дополнительная информация о шаблонах<глава_78_start>`). В этой главе мы рассмотрели следующие
что мы рассмотрели в этой главе:
* Шаблоны определяют код как шаблон, чтобы компилятор мог генерировать его экземпляры
его в соответствии с реальным использованием в программе.
* Шаблоны - это функция времени компиляции.
* Достаточно указать списки параметров шаблона, чтобы сделать шаблонами функции, структуры и
определения классов шаблонами.

.. code-block:: d

    void functionTemplate(T)(T functionParameter) {
    // ...
    }
    class ClassTemplate(T) {
    //
    } ...

* Аргументы шаблона могут быть указаны явно после восклицательного знака.
  Скобки не нужны, если внутри скобок находится только одна лексема
  скобки.

.. code-block:: d

    auto object1 = new ClassTemplate!(double);
    auto object2 = new ClassTemplate!double; // same thing

* Каждый инстанс шаблона дает отдельный тип.

.. code-block:: d

    assert(typeid(ClassTemplate!int) !=
    typeid(ClassTemplate!uint));

* Аргументы шаблона могут быть выведены только для шаблонов функций

.. code-block:: d

    functionTemplate(42); // functionTemplate!int is deduced

Шаблоны могут быть специализированы для типа, который находится после символа :.

.. code-block:: d

    class ClassTemplate(T : dchar) {
    // ...
    }

Аргументы шаблона по умолчанию указываются после символа =.

.. code-block:: d

    void functionTemplate(T = long)(T functionParameter) {
    // ...
    }
